# -*- coding: utf-8 -*-
"""
@Time ： 2023/6/25 22:43
@Auth ： 叶东宇
@File ：implementQueueUsingStacks.py
"""
from collections import deque
class MyStackUsingQueue:
    """
    栈只能从尾部添加数据，从尾部拿数据
    但是队列（list）只能从尾部添加数据，同头拿数据
    """

    def __init__(self):
        """
        用的队列实现栈，那么用list时只能从尾部添加数据，从头部拿数据
        """
        self.queue_in = []
        self.queue_out = []

    def push(self, x):
        self.queue_in.append(x)

    """
    注意：
    栈只能从尾部添加数据，从尾部拿数据
    但是队列（list）只能从尾部添加数据，同头部拿数据
    因此当这个栈添加了一些数据之后，其实都存储在queue_in中
    当我们想拿到最顶上（最后部）的数据时，我们不能直接从尾部拿，因为queue只能从头部拿数据
    所以要先把除顶部的数据全部移到queue_out中，然后queue_in中的最后一个数据就是top了，也是要pop的对象
    然后还要把所有在queue_out中的数据全部转移到queue_in中
    
    但是这里有个更简便的方法：把queue_in和queue_out的数据直接交换（交换变量的引用即可），这样会快很多
    """
    def pop(self):
        if self.empty():
            return None
        if len(self.queue_in) == 1:
            return self.queue_in.pop(0)
        elif len(self.queue_in) > 1:
            for i in range(len(self.queue_in)-1):
                self.queue_out.append(self.queue_in.pop(0))
            tmp = self.queue_in.pop(0)
            # for i in range(len(self.queue_out)):
            #     self.queue_in.append(self.queue_out.pop(0))
            self.queue_in, self.queue_out = self.queue_out, self.queue_in
            return tmp

    def top(self):
        tmp = self.pop()
        self.queue_in.append(tmp)
        return tmp

    def empty(self):
        return len(self.queue_in)==0 and len(self.queue_out)==0

class MyStack:
    def __init__(self):
        self.que = deque()

    def push(self, x: int) -> None:
        self.que.append(x)

    def pop(self) -> int:
        if self.empty():
            return None
        for i in range(len(self.que)-1):
            self.que.append(self.que.popleft())
        return self.que.popleft()

    def top(self) -> int:
        if self.empty():
            return None
        return self.que[-1]

    def empty(self) -> bool:
        return not self.que

if __name__ == "__main__":
    a = MyStackUsingQueue()
    print(a.push(1))
    print(a.push(2))
    print(a.top())
    print(a.pop())
    print(a.empty())